//给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
//
// 
// 
// 
// 
// 
//
// 示例 1： 
// 
// 
//输入：head = [1,2,3,4,5]
//输出：[5,4,3,2,1]
// 
//
// 示例 2： 
// 
// 
//输入：head = [1,2]
//输出：[2,1]
// 
//
// 示例 3： 
//
// 
//输入：head = []
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// 链表中节点的数目范围是 [0, 5000] 
// -5000 <= Node.val <= 5000 
// 
//
// 
//
// 进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？ 
//
// Related Topics 递归 链表 👍 3412 👎 0


package leetcode.editor.cn;

import leetcode.editor.cn.structure.ListNode;

/**
 * 反转链表
 * @author CodeTheory
 * @date 2023-11-06 18:31:49
 */
public class P206_ReverseLinkedList{
	 public static void main(String[] args) {
	 	 Solution solution = new P206_ReverseLinkedList().new Solution();
	 }
	 
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
	public ListNode reverseList(ListNode head) {
		if (head == null || head.next == null) {
			return head;
		}
		ListNode newListNode = reverseList(head.next);
		head.next.next = head;
		head.next = null;
		return newListNode;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
// 迭代法
//	public ListNode reverseList(ListNode head) {
//		ListNode temp = null;
//		ListNode prev = null;
//		while(head != null) {
//			temp = head.next;
//			head.next = prev;
//			prev = head;
//			head = temp;
//		}
//		return prev;
//	}

// 递归法 从左往右
//public ListNode reverseList(ListNode head) {
//	return reverse(null, head);
//}
//
//	private ListNode reverse(ListNode prev, ListNode curr) {
//		if (curr == null) {
//			return prev;
//		}
//		ListNode temp = curr.next;
//		curr.next = prev;
//		return reverse(curr, temp);
//	}

// 递归 从右往左
//public ListNode reverseList(ListNode head) {
//	if (head == null || head.next == null) {
//		return head;
//	}
//	ListNode newListNode = reverseList(head.next);
//	head.next.next = head;
//	head.next = null;
//	return newListNode;
//}